﻿/*
题目: 累加序列

给定一个字符串形式的数字序列，请问能否由这个字符串拆分成一个累加序列。
累加序列：至少包含三个数，除了最开始的两个数外，每个数都是前两个数之和。
如果能则输出 true，否则输出 false

0≤val≤9  ，不能含有前导零

https://www.nowcoder.com/practice/ff244079fdaf4d8f9767887ec9582043
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    bool AdditiveArray(string str) {
        vector<int> res;
        return dfs(str, 0, res) && res.size() >= 3;
    }

    bool dfs(string& str, int pos, vector<int>& res) {
        if (pos >= str.size())  return true;

        for (int i = pos; i < str.size(); i++) {
            long long num = stoll(str.substr(pos, i - pos + 1));
            if (num >= INT_MAX)     return false;
            if (res.size() >= 2) {
                if (num == res[res.size() - 1] + res[res.size() - 2]) {
                    res.emplace_back(num);
                    if (dfs(str, i + 1, res) == true)   return true;

                    res.pop_back();
                }
                if (num > res[res.size() - 1] + res[res.size() - 2])   return false;
            }
            else if (res.size() < 2) {
                res.emplace_back(num);
                if (dfs(str, i + 1, res) == true)   return true;

                res.pop_back();
            }
        }

        return false;
    }
};
